package com.future.offer;

/**
 * Description: 剑指 Offer II 102. 加减的目标值
 *
 * @author weiruibai.vendor
 * Date: 2022/12/26 15:43
 */
public class Solution_102 {

    static Solution_102 instance = new Solution_102();

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        Integer target = 3;
        System.out.println(instance.findTargetSumWays(nums, target));
    }

    public int findTargetSumWays(int[] nums, int target) {
        return process(nums, nums[0], 1, target) + process(nums, -nums[0], 1, target);
    }

    private int process(int[] nums, int sum, int i, int target) {
        if (i >= nums.length) {
            return sum == target ? 1 : 0;
        }
        return process(nums, sum + nums[i], i + 1, target) + process(nums, sum - nums[i], i + 1, target);
    }
}
